import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-19
 * Time: 21:36
 */

public class Solution {
    /**
     *  方法一: 双指针
     */
    public int[] twoSum1(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left+1, right+1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }

    /**
     *  方法二: 二分查找
     */
    public int[] twoSum2(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }


    /**
     *  方法三: 使用 哈希表
     */
    public int[] twoSum3(int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < numbers.length;i++) {
            int value = target - numbers[i];
            if (map.containsKey(value)) {
                return new int[]{map.get(value)+1, i+1};
            }
            map.put(numbers[i], i);
        }
        return new int[]{-1, -1};
    }
}
